package com.lcm.algorithm.datatest.dp.knapsack.unbounded;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description:
 * 322. 零钱兑换
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回 -1。
 *
 * 示例 1:
 * 输入: coins = [1, 2, 5], amount = 11
 * 输出: 3
 * 解释: 11 = 5 + 5 + 1
 *
 * 示例 2:
 * 输入: coins = [2], amount = 3
 * 输出: -1
 *
 * @author: lcm
 * @create: 2020-04-25 16:04
 **/

public class CoinChange {

    public static void main(String[] args){
        System.out.println(coinChange1(new int[]{1,2,5},11));
        System.out.println(coinChange2(new int[]{1,2,5},11));
        CoinChange coinChange=new CoinChange();
    }

    /**
     * f(i,C)=Min(f(i-1,C-x*ci)+x) 0=<x<=C/ci
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange1(int[] coins, int amount) {
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<coins.length;i++){
            int t=amount/coins[i];
            for(;t>0;t--){
                list.add(coins[i]);
            }
        }
        if(list.isEmpty()) {
            return -1;
        }

        int[] dp=new int[amount+1];
        for(int i=0;i<list.size();i++){
            for(int j=amount;j>=list.get(i);j--){
                if(dp[j-list.get(i)]!=-1){
                    dp[j]=Math.max(dp[j],dp[j-list.get(i)]+1);
                }
            }
        }

        return dp[amount]==0?-1:dp[amount];
    }

    /**
     * 记忆化搜索
     */
    public static int coinChange2(int[] coins, int amount) {
        return help(coins,amount);
    }
    static Map<Integer,Integer> map=new HashMap<>();
    static int help(int[] coins, int amount){
        if(map.containsKey(amount)) {
            return map.get(amount);
        }
        if(amount==0) {
            return 0;
        }
        if(amount<0){
            return -1;
        }
        int result=Integer.MAX_VALUE;
        for(int i=0;i<coins.length;i++){
            int temp=help(coins,amount-coins[i]);
            if(temp!=-1){
                result=Math.min(result,temp+1);
            }
        }
        if(result==Integer.MAX_VALUE){
            result=-1;
        }
        map.put(amount,result);
        return result;
    }

}
